package com.hw.algorithm.leetcode.array;

/**
 * @author hewei
 * <h>题目描述：4. 寻找两个正序数组的中位数</h>
 * <p>
 *     给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
 *
 * 算法的时间复杂度应该为 O(log (m+n)) 。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：nums1 = [1,3], nums2 = [2]
 * 输出：2.00000
 * 解释：合并数组 = [1,2,3] ，中位数 2
 * 示例 2：
 *
 * 输入：nums1 = [1,2], nums2 = [3,4]
 * 输出：2.50000
 * 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/median-of-two-sorted-arrays
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * </p>
 * <h>题解</h>
 * <p>
 *     1.主要是归并排序的思想，将两个有数组归并为一个有序数组
 *     2.最终数组的个数：  偶数，返回 中间两个值的平均值 ；奇数，直接返回中间的值
 *     3.注意：在计算的时候 整数之间的计算会忽略小数部分，所以在求平均数时需要将相除的两部分转为 double 类型。
 * </p>
 */
public class LeetCodeArray4 {
    public static void main(String[] args) {

        int[] a = {2,4,5,9};
        int[] b = {1,3,6,7,9,10};
        System.out.println(findMedianSortedArrays(a,b));
    }
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] nums=new int[nums1.length+nums2.length];
        int i=0,j=0,k=0;
        while(i<nums1.length && j<nums2.length){
            if(nums1[i] <= nums2[j]){
                nums[k++]=nums1[i++];
            }else{
                nums[k++]=nums2[j++];
            }
        }
        while(i<nums1.length){
            nums[k++]=nums1[i++];
        }
        while(j<nums2.length){
            nums[k++]=nums2[j++];
        }
        for (int t = 0; t <nums.length;t++){
            System.out.print(nums[t]+" " );
        }
        System.out.println();
        int mid=nums.length / 2;
        if(nums.length % 2 ==0){
            return (nums[mid]+nums[mid-1]) / 2.0;
        }else{
            return nums[mid];
        }
    }
}